/**
 * 排序算法
 * 冒泡: 大的往后排, 两两比较 时间复杂度O(n^2)
 * 插入：小的往前排, 核心思想是将一个数据插入到已经排好序的有序数据中， 时间复杂度O(n^2)
 * 选择：小的往前排， 选择最小的放在最前面， 时间复杂度O(n^2)
 * 
 * 希尔： 插入排序的改进版,时间复杂度O(n^1.3)
 * 快速： 时间复杂度O(nlogn)
 */

class Sort {
    constructor(data) {
        this.data = data;
    }
    swap(i, j) {
        let temp = this.data[i];
        this.data[i] = this.data[j];
        this.data[j] = temp;
    }
    media(data) {
        let mid = Math.floor(data.length / 2);
        if (data[0] > data[mid]) {
            this.swap(0, mid);
        }
        if (data[mid] > data[data.length - 1]) {
            this.swap(mid, data.length - 1);
        }
        if (data[0] > data[mid]) {
            this.swap(0, mid);
        }
        return mid;
    }
    bubble() {
        for (let i = 0; i < this.data.length - 1;i ++) {
            for (let j = i + 1; j < this.data.length;j ++) {
                if (this.data[i] > this.data[j]) {
                    this.swap(i, j);
                }
            }
        }
        return this.data
    }
    choose() {
        for (let i = 0; i < this.data.length - 1; i ++) {
            let min = i
            for (let j = i + 1;j < this.data.length;j ++) {
                if (this.data[min] > this.data[j]) {
                    min = j;
                }
            }
            this.swap(i, min);
        }
        return this.data
    }
    insert() {
        for (let i = 1;i < this.data.length;i ++) {
            let temp = this.data[i], j = i

            while(j >= 0 && temp < this.data[j - 1]) {
                this.data[j] = this.data[j - 1];
                j --;
            }
            this.data[j] = temp;
        }
        return this.data
    }
    sheel() {
        let gap = Math.floor(this.data.length / 2);
        while( gap > 0) {
            for (let i = gap;i < this.data.length;i ++) {
                let temp = this.data[i], j = i;
                while( j - gap >= 0 && temp < this.data[j - gap]) {
                    this.data[j] = this.data[j - gap];
                    j -= gap;
                }
                this.data[j] = temp;
            }
            gap = Math.floor(gap / 2);
        }
        return this.data
    }
    quick(data) {
        data = data || this.data;

        if (data.length <= 1) {
            return data;
        }
        let mid = this.media(data);
        let left = [], right = [];
        for (let i = 0; i < data.length; i ++) {
            if (i !== mid) {
                if (data[i] < data[mid]) {
                    left.push(data[i]);
                } else {
                    right.push(data[i]);
                }
            }
        }
        return this.quick(left).concat(data[mid], this.quick(right));
    }
}

let sort = new Sort([-2, -1, 3, 2, 1, 4, 5, -1]);
// console.log('冒泡排序', sort.bubble()); 
// console.log('\n选择排序', sort.choose());
// console.log('\n插入排序', sort.insert()); 
console.log('\n希尔排序', sort.sheel());
console.log('\n快速排序', sort.quick());